#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <time.h>  // 用于随机数种子

// 大整数类型（避免溢出，适配模运算）
typedef uint64_t bigint;

/**
 * 二进制快速幂：计算 (base^power) mod n（修正Python逻辑，补充取模避免溢出）
 * 注：Python原版未实时取模，C语言需补充以防止64位整数溢出
 */
bigint binary_exponentiation(bigint base, bigint power, bigint n) {
    bigint power_2 = 1;
    bigint r = 1;
    bigint p = base % n;  // 初始底数取模，缩小范围

    // 对应Python的 while (power_2 := power_2 << 1) <= power
    while ((power_2 <<= 1) <= power) {
        p = (p * p) % n;  // 底数平方后取模，避免溢出
        if ((power_2 & power) != 0) {  // 按位与判断当前位是否为1
            r = (r * p) % n;          // 结果累乘后取模
        }
    }
    return r;
}

/**
 * 费马质数检验：判断n是否为质数（大概率正确，存在伪素数误判）
 * @param n: 待检验的数
 * @return: true-大概率是质数，false-一定是合数
 */
bool is_prim(bigint n) {
    // 小范围特殊判断：n<=4时，仅2、3是质数
    if (n <= 4) {
        return (n == 2 || n == 3);
    }

    // 初始化随机数种子（仅初始化一次）
    static bool seed_init = false;
    if (!seed_init) {
        srand((unsigned int)time(NULL));
        seed_init = true;
    }

    // 5次随机检验（对应Python的range(5)）
    for (int i = 0; i < 5; i++) {
        // 生成随机底数a：2 <= a <= n-1（Python的random.randint(2, n)，修正为n-1避免a=n时mod n=0）
        bigint a = 2 + (rand() % (n - 2));  // rand()%m 生成 [0, m-1]，此处m = n-2，故a范围[2, n-1]

        // 计算 a^(n-1) mod n
        bigint r = binary_exponentiation(a, n - 1, n);

        // 费马小定理：若n是质数，则a^(n-1) ≡ 1 mod n；若不等于1，n一定是合数
        if (r != 1) {
            return false;
        }
    }

    // 5次检验均通过，大概率是质数
    return true;
}

// 测试主函数（对应Python的4个测试用例）
int main() {
    bigint test_nums[] = {10000, 911, 561, 341};
    int test_count = sizeof(test_nums) / sizeof(test_nums[0]);

    for (int i = 0; i < test_count; i++) {
        bigint n = test_nums[i];
        bool result = is_prim(n);
        printf("is_prim(%llu) = %s\n", n, result ? "True" : "False");
    }

    return 0;
}